package com.zjsru.plan2023.oneday;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: cookLee
 * @Date: 2023-11-20
 * 数位和相等数对的最大和
 */
public class MaximumSum {
    /**
     * 主要
     * \
     * 输入：nums = [18,43,36,13,7]
     * 输出：54
     * 解释：满足条件的数对 (i, j) 为：
     * - (0, 2) ，两个数字的数位和都是 9 ，相加得到 18 + 36 = 54 。
     * - (1, 4) ，两个数字的数位和都是 7 ，相加得到 43 + 7 = 50 。
     * 所以可以获得的最大和是 54 。
     * \
     * 输入：nums = [10,12,19,14]
     * 输出：-1
     * 解释：不存在满足条件的数对，返回 -1 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MaximumSum maximumSum = new MaximumSum();
        int[] nums = new int[]{18,43,36,13,7};
        System.out.println(maximumSum.maximumSum2(nums));
    }

    /**
     * 最大总和：模拟
     * 由于使用双循环，如果碰到大量测试数据，时间会很慢
     * @param nums nums
     * @return int
     */
    public int maximumSum(int[] nums) {
        int len = nums.length;
        int ans = -1;
        for (int i = 0; i < len; i++) {
            int sum = this.helper(nums[i]);
            for (int j = i + 1; j < len; j++) {
                if(this.helper(nums[j]) == sum){
                    ans = Math.max(ans,nums[i] + nums[j]);
                }
            }
        }
        return ans;
    }

    /**
     * 获取位数助手类
     *
     * @param num num
     * @return int
     */
    private int helper(int num) {
        int ans = 0;
        while (num > 0) {
            ans += num % 10;
            num = num / 10;
        }
        return ans;
    }

    /**
     * 方法二：哈希表
     *
     * @param nums nums
     * @return int
     */
    public int maximumSum2(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int ans = -1;
        for (int num : nums) {
            int sum = this.helper(num);
            if (countMap.containsKey(sum)) {
                ans = Math.max(ans, countMap.get(sum) + num);
                //这一步需要重新更新当前位数和的map的value值,以便保留最大值
                countMap.put(sum,Math.max(countMap.get(sum),num));
            } else {
                countMap.put(sum, num);
            }
        }
        return ans;
    }

    /**
     * 模拟：使用int数组代替哈希表
     *
     * @param nums nums
     * @return int
     */
    public int maximumSum3(int[] nums) {
        //int 位数和不会超过100
        int[] val = new int[100];
        int ans = -1;
        for (int num : nums) {
            int sum = this.helper(num);
            //此时说明已经存入一个相同位数和的值
            if (val[sum] != 0) {
                ans = Math.max(ans, val[sum] + num);
            }
            val[sum] = Math.max(val[sum], num);
        }
        return ans;
    }

}
